package org.jheaps.array

import org.jheaps.Constants
import org.jheaps.ValueHeap
import org.jheaps.annotations.ConstantTime
import org.jheaps.annotations.LogarithmicTime
import java.io.Serializable
import kotlin.math.max

/**
 * An optimized array-based binary heap with integer keys.
 *
 *
 *
 * This is a highly optimized implementation which uses (a) the Wegener
 * bottom-up heuristic and (b) sentinel values. The implementation uses an array
 * in order to store the elements, providing amortized O(log(n)) time for the
 * `insert` and `deleteMin` operations. Operation `findMin`,
 * is a worst-case O(1) operation. All bounds are worst-case if the user
 * initializes the heap with a capacity larger or equal to the total number of
 * elements that are going to be inserted into the heap.
 *
 *
 *
 * See the following papers for details about the optimizations:
 *
 *  * Ingo Wegener. BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on
 * an average, QUICKSORT (if n is not very small). Theoretical Computer Science,
 * 118(1), 81--98, 1993.
 *  * Peter Sanders. Fast Priority Queues for Cached Memory. Algorithms
 * Engineering and Experiments (ALENEX), 312--327, 1999.
 *
 *
 *
 *
 * **Note that this implementation is not synchronized.** If
 * multiple threads access a heap concurrently, and at least one of the threads
 * modifies the heap structurally, it *must* be synchronized externally.
 * (A structural modification is any operation that adds or deletes one or more
 * elements or changing the key of some element.) This is typically accomplished
 * by synchronizing on some object that naturally encapsulates the heap.
 *
 * @param <V>
 * the type of values maintained by this heap
 *
 * @author Dimitrios Michail
</V> */
class BinaryArrayIntegerValueHeap<V> @JvmOverloads constructor(capacity: Int = DEFAULT_HEAP_CAPACITY) :
    ValueHeap<Int, V>, Serializable {
    /**
     * The array used for representing the heap.
     */
    private var array: Array<Elem<V>?>

    /**
     * Number of elements in the heap.
     */
    private var size: Int

    /**
     * Minimum capacity due to initially requested capacity.
     */
    private val minCapacity: Int

    /**
     * Constructs a new, empty heap, with a provided initial capacity using the
     * natural ordering of its keys.
     *
     *
     *
     * The initial capacity of the heap is provided by the user and is adjusted
     * automatically based on the sequence of insertions and deletions. The
     * capacity will never become smaller than the initial requested capacity.
     *
     * @param capacity
     * the initial heap capacity
     */
    /**
     * Constructs a new, empty heap, using the natural ordering of its keys.
     *
     *
     *
     * The initial capacity of the heap is [.DEFAULT_HEAP_CAPACITY] and
     * adjusts automatically based on the sequence of insertions and deletions.
     */
    init {
        checkCapacity(capacity)
        this.minCapacity = max(capacity.toDouble(), DEFAULT_HEAP_CAPACITY.toDouble())
            .toInt()
        //this.array = java.lang.reflect.Array.newInstance(Elem::class.java, minCapacity + 2) as Array<Elem<V>>
        this.array = arrayOfNulls(minCapacity + 2)
        array[0] = Elem(INF_KEY, null)
        for (i in 1 until (minCapacity + 2)) {
            array[i] = Elem(SUP_KEY, null)
        }
        this.size = 0
    }

    @get:ConstantTime
    override val isEmpty: Boolean
        get() {
            return size == 0
        }

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun size(): Long {
        return size.toLong()
    }

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun clear() {
        size = 0
    }

    /**
     * {@inheritDoc}
     */
    override fun comparator(): Comparator<in Int?>? {
        return null
    }

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun findMin(): Int {
        if (Constants.NOT_BENCHMARK && size == 0) {
            throw NoSuchElementException()
        }
        return array[1]!!.key
    }

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun findMinValue(): V {
        if (Constants.NOT_BENCHMARK && size == 0) {
            throw NoSuchElementException()
        }
        return array[1]!!.value!!
    }

    /**
     * {@inheritDoc}
     */
    @LogarithmicTime
    override fun insert(key: Int, value: V?) {
        if (Constants.NOT_BENCHMARK) {
            if (key == null) {
                throw NullPointerException("Null keys not permitted")
            }
            // make space if needed
            if (size == array.size - 2) {
                if (array.size == 2) {
                    ensureCapacity(1)
                } else {
                    ensureCapacity(2 * (array.size - 2))
                }
            }
        }

        ++size
        var hole: Int = size
        var pred: Int = hole shr 1
        var predElem = array[pred]!!

        while (predElem.key > key) {
            array[hole]!!.key = predElem.key
            array[hole]!!.value = predElem.value

            hole = pred
            pred = pred shr 1
            predElem = array[pred]!!
        }

        array[hole]!!.key = key
        array[hole]!!.value = value
    }

    /**
     * {@inheritDoc}
     */
    @LogarithmicTime
    override fun insert(key: Int) {
        insert(key, null)
    }

    /**
     * {@inheritDoc}
     */
    @LogarithmicTime
    override fun deleteMin(): Int {
        if (Constants.NOT_BENCHMARK && size == 0) {
            throw NoSuchElementException()
        }

        val result: Int = array[1]!!.key

        // first move up elements on a min-path
        var hole: Int = 1
        var succ: Int = 2
        val sz: Int = size
        while (succ < sz) {
            val key1: Int = array[succ]!!.key
            val key2: Int = array.get(succ + 1)!!.key
            if (key1 > key2) {
                succ++
                array[hole]!!.key = key2
                array[hole]!!.value = array[succ]!!.value
            } else {
                array[hole]!!.key = key1
                array[hole]!!.value = array[succ]!!.value
            }
            hole = succ
            succ = succ shl 1
        }

        // bubble up rightmost element
        val bubble: Int = array[sz]!!.key
        var pred: Int = hole shr 1
        while (array[pred]!!.key > bubble) {
            array[hole]!!.key = array[pred]!!.key
            array[hole]!!.value = array[pred]!!.value
            hole = pred
            pred = pred shr 1
        }

        // finally move data to hole
        array[hole]!!.key = bubble
        array[hole]!!.value = array[sz]!!.value

        array[size]!!.key = SUP_KEY
        array[size]!!.value = null
        size = sz - 1

        if (Constants.NOT_BENCHMARK) {
            // free unused space
            val currentCapacity: Int = array.size - 2
            if (2 * minCapacity <= currentCapacity && 4 * size < currentCapacity) {
                ensureCapacity(currentCapacity / 2)
            }
        }

        return result
    }

    /**
     * Ensure that the array representation has the necessary capacity.
     *
     * @param capacity
     * the requested capacity
     */
    private fun ensureCapacity(capacity: Int) {
        checkCapacity(capacity)
        //val newArray: Array<Elem<V>?> = java.lang.reflect.Array.newInstance(Elem::class.java, capacity + 2) as Array<Elem<V?>>
        val newArray: Array<Elem<V>?> = arrayOfNulls(capacity + 2)
        if (newArray.size >= array.size) {
            System.arraycopy(array, 0, newArray, 0, array.size)
            for (i in array.size until newArray.size) {
                newArray[i] = Elem(SUP_KEY, null)
            }
        } else {
            System.arraycopy(array, 0, newArray, 0, newArray.size)
        }
        array = newArray
    }

    /**
     * Check that a capacity is valid.
     *
     * @param capacity
     * the capacity
     *
     * @throws IllegalArgumentException
     * if the capacity is negative or more than the maximum array
     * size
     */
    private fun checkCapacity(capacity: Int) {
        if (capacity < MIN_HEAP_CAPACITY) {
            throw IllegalArgumentException("Heap capacity must be >= " + MIN_HEAP_CAPACITY)
        }
        if (capacity > MAX_HEAP_CAPACITY) {
            throw IllegalArgumentException("Heap capacity too large")
        }
    }

    private class Elem<V>(var key: Int, var value: V?) : Serializable {}

    companion object {
        private val serialVersionUID: Long = 1L

        /**
         * Default initial capacity of the heap.
         */
        val DEFAULT_HEAP_CAPACITY: Int = 16

        /**
         * Supremum
         */
        private val SUP_KEY: Int = Int.MAX_VALUE

        /**
         * Infimum
         */
        private val INF_KEY: Int = Int.MIN_VALUE

        /**
         * The maximum heap capacity.
         */
        private val MAX_HEAP_CAPACITY: Int = Int.MAX_VALUE - 8 - 1

        /**
         * The minimum heap capacity.
         */
        private val MIN_HEAP_CAPACITY: Int = 0
    }
}
